/*
 *      Copyright: Bernd Schubert <bschubert@ddn.com>
 *      License: GPLv3
*/

#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <ext2fs/ext2_fs.h>
#include <ext2fs/ext2fs.h>
#include <linux/fs.h>
#include <linux/xattr.h>

#include "sd.h"
#include "hash.h"

static opts_t opts;
static dir_block_table_t blocks;
#define CWD_MAX (1024 * 16)
static char cwd[CWD_MAX];

#define DIR_MODE S_IRUSR | S_IWUSR | S_IXUSR | S_IRGRP | S_IXGRP | S_IROTH | S_IXOTH
#define FILE_MODE S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH

// forward declaration
static unsigned walk_block(block_t *block);

// keep track of links in top-level blocks, create after block created
static dentry_t *block_symlink_p = NULL;

static void queue_link(dentry_t *d) {
	d->symlink_next = block_symlink_p;
	block_symlink_p = d;
}

void fmt_dentry_path(char *buf, dentry_t *dentry) {
	block_t *b = dentry->block;

	// need to look at tl block for uid_dir prefixes
	snprintf(buf, CWD_MAX - 1, "/%s/%s/%s/%s", 
			(b->tl_block) ? b->tl_block->cwd : "",
			b->cwd,
			b->name,
			dentry->name);
	buf[CWD_MAX - 1]  = 0;
}

void the_usage(char *progname)
{
	fprintf(stderr, "\nUsage: %s [-b block_size] [-s superblock] -o outputdir -t ost_data_file <file/device> \n\n", progname);
}

/**
 *  Allocate a single directory entry
 */
dentry_t *alloc_dentry(void)
{
	dentry_t *dentry = malloc(sizeof(dentry_t));
	if (dentry == NULL) {
		fprintf(stderr, "Could not alloc dentry\n");
		exit(1);
	}
	
	memset(dentry, 0, sizeof(dentry_t));

	dentry->childs.child = NULL;
	dentry->childs.num = 0;
	dentry->next = NULL;

	return dentry;
}

/**
 * Add further entries to the blocks table
 */
static void realloc_blocks(int num)
{
	static int first = true;

	if (first) {
		first = false;
		blocks.table = NULL;
		blocks.n_entries = 0;
		blocks.n_alloc = 0;
	}

	blocks.n_alloc += num;
	blocks.table = realloc(blocks.table, sizeof(block_t) * blocks.n_alloc);
	if (blocks.table == NULL) {
		fprintf(stderr, "realloc failed: %s\n",
				strerror(errno));
		exit(1);
	}
}

/**
 * parse command line options
 */
static void parse_opts(int argc, char **argv)
{
	int c;

	if (argc != 7) {
		fprintf(stderr, "argc doesn't match expected %d, got %d\n",
			7, argc);
		the_usage(argv[0]);
		exit(1);
	}

	opts.block_size = 4096;
	opts.sb = 0;
	opts.fname = NULL;
	opts.outputdir = NULL;
	opts.ost_data_file = NULL;

	while ((c = getopt (argc, argv, "b:m:o:s:t:")) != EOF) {
		switch (c) {
		case 'b':
			opts.block_size = atoi(optarg);
			break;
		case 'm':
			opts.mapping_file = strdup(optarg);
		case 'o':
			opts.outputdir = strdup(optarg);
			break;
		case 's':
			opts.sb = atoll(optarg);
			break;
		case 't':
			opts.ost_data_file = strdup(optarg);
			break;
		default:
			the_usage(argv[0]);
			exit(1);
		}
	}

	opts.fname = strdup(argv[optind++]);

	// TODO check if we have all options
}

static void print_dir_entry(struct ext2_dir_entry_2 *entry, block_t *block)
{
	static bool first = true;
	char name[EXT2_NAME_LEN + 1];

	snprintf(name, entry->name_len + 1, "%s", entry->name);
	
	if (first) {
		first = false;
		printf("%s  %20s	%s	%s	%s	%s\n",
		"blk_nr", "name", "inode", "f_type",
		"dir_inode", "parent");
	}

	printf("%lu	%20s	%d	%d		%ld	%ld\n",
			block->number, name, entry->inode, entry->file_type,
			block->dir_inode, block->parent);
}

/**
 * most people will use the plain ascii alphabet for their filenames,
 * especially in the US, we simply declare only those files as valid
 */
static bool check_char(int character)
{
	// now the difficult part, scan for valid filename characters
	// we skip that for now, since all the maths above already might
	// protect us
	if (character < '+')
		return false; // very unlikely char

	if (character == '/')
		return false;

	/*
		if (entry->name[0] > 47 && entry->name[0] < 65)
			return false; // unlikely char

		if (entry->name[0] > 90 && entry->name[0] < 97)
			return false; // unlikely char
	*/

	if (character > 'z') // 122
		return false; // unlikely char
	
	return true;
}

/**
 * is_dir_entry - check if really a dir entry
 * unfortunately directory entries do NOT have a magic to detect
 * if it is really a directory entry :(
 * So we have use the file_type and file name to do a heuristic detection
 * This is not perfectly reliable, of course :(
 */
static bool is_dir_entry(struct ext2_dir_entry_2 *entry, off_t offset)
{
	int calculated_rec_len;
	int min_name_len = 1; // minimal 1 character for the filename (not \0 terminated)
	int padding;
	int pos; // position within a suspected dentry
	int count;
	int character;

	// struct ext2_dir_entry_2, but name_len_min
	int min_rec_len = 4 + 2 + 1 + 1 + min_name_len;
	int max_rec_len = opts.block_size - offset; 
	
	if (entry->inode == 0)
		return false;

	if (entry->file_type == EXT2_FT_UNKNOWN || entry->file_type > 7)
		return false; // incorrect file type

	if (entry->rec_len < min_rec_len || entry->rec_len > max_rec_len) {
		return false; // rec_len is not sane
	}

	if (entry->name_len < min_name_len)
		return false; // name_len is not sane

	calculated_rec_len = 4 + 2 + 1 + 1 + entry->name_len;
	padding = 4 - (calculated_rec_len % 4);
	if (padding == 4 )
		padding = 0;
	calculated_rec_len += padding;

	// We can't check for the exact rec_len, since rec_len is increased
	// if a dir-entry following the present dir-entry is deleted
	// (increased by deleted dir_entry)
	if (entry->rec_len < calculated_rec_len )
		return false;

	// check if the filename is valid and we simply assume here that the filename
	// is not longer than 128 chars
	pos = min_rec_len - 1;
	count = 0;
	while (pos < max_rec_len && count < 128) {
		// check if entry->name_len is correct
		character = entry->name[count];
		
		if (check_char(character) == false)
			return false;
			
		
		count++;
		pos++;

		if (entry->name_len == count)
			return true;
	}
	return false;
}

/**
 * check if the dir_entry is valid according to OST data
 */
static bool check_dentry_with_osts(struct ext2_dir_entry_2 *dir_entry)
{
	switch (dir_entry->file_type) {

	case EXT2_FT_REG_FILE:
		// regular files should be known to OSTs
		if (!hash_find_fid(dir_entry->inode)) {
			// So we got a file, but it is unknown on the OSTs
			// we can silently ignore it
			return false;
		}
		break;
	case EXT2_FT_DIR:
		if (hash_find_fid(dir_entry->inode)) {
			// D'oh, we've got a directory, which shouldn't have
			// an inode on OSTs. **Probably** this directory was deleted 
			// and the inode was recycled, we ignore it silently!
			return false;
		}
		break;
	default:
		if (hash_find_fid(dir_entry->inode)) {
			// This is the difficult part now. We shouldn't 
			// have OST inodes for files other than EXT2_FT_REG_FILE (AFAIK)
			// The admin has to decide in this case
			fprintf(stderr, "Unexpected inode %u on OST found, file type %d\n", 
				dir_entry->inode, dir_entry->file_type);
		}
	}
	
	return true;
}

/**
 * scan_block	scan through block for dir entries
 */
static int scan_block(void *buf, uint64_t blk_nr)
{
	off_t offset = 0;
	struct ext2_dir_entry_2 *dir_entry;
	int dentry_size = sizeof(struct ext2_dir_entry_2);
	int64_t curdir_inode = -1, parent = -1;
	block_t *block = NULL;
	dentry_t *dentry = NULL;

	while (offset + dentry_size <= opts.block_size) {
		dir_entry = buf + offset;  // implicit typecast
		bool is_dot = false;
		dentry_t *previous_dentry;
		
		if (is_dir_entry(dir_entry, offset)) { // found a valid dentry
			// increase offset already here since we might simply call
			// 'continue' and forget to do it later on
			offset += dir_entry->rec_len; 

			if (check_dentry_with_osts(dir_entry) == false)
				continue;
			
			if (block == NULL) {
				if (blocks.n_entries == blocks.n_alloc)
					realloc_blocks(1000);
				block = &blocks.table[blocks.n_entries];
				dentry = alloc_dentry();
				block->first = dentry;
				block->parent = -1;
				block->dir_inode = 0;
				block->name = NULL;
				block->number = blk_nr;
				block->uid = -1;
				block->gid = -1;
				block->walked = 0;
				block->tl_block = 0;
				block->cwd = 0;
				blocks.n_entries++;
			} else {
				// check if dentry is used and only if so 
				// allocate a new dentry
				if (dentry->name) {
					previous_dentry = dentry;
					dentry->next = alloc_dentry();
					dentry = dentry->next;
					dentry->next = NULL;
				}
				
			}

			// if dentry is ".", then we know the inode of this dir
			if (dir_entry->name[0] == '.' && dir_entry->name_len == 1) {

				if (curdir_inode != -1) {
					// never should happen for blocks
					fprintf(stderr, "unexpected . dentry after dentry!\n");
				}
				block->dir_inode = dir_entry->inode;
				is_dot = true;
			}

			if ((strncmp(dir_entry->name, "..", 2) == 0)
					&&   dir_entry->name_len == 2) {

				if (parent != -1) {
					// never should happen for blocks
					fprintf(stderr, "unexpected .. dentry after dentry!\n");
				}
				
				if (dir_entry->inode == block->dir_inode) {
					// linked to itself, probably root, ignore it
					fprintf(stderr, ".. of %lu linked to itself\n", block->dir_inode);
					// free(dentry); //malloc freaks out
					previous_dentry->next = NULL;
					continue;
				}
				
				block->parent = dir_entry->inode;
				is_dot = true;
			}

			dentry->inode = dir_entry->inode;
			dentry->name = malloc(dir_entry->name_len + 1);
			if (dentry->name == NULL) {
				fprintf(stderr, "dentry->name alloc failed: %s\n",
						strerror(errno));
				exit(1);
			}
			snprintf(dentry->name, dir_entry->name_len + 1, "%s", dir_entry->name);
			dentry->type = dir_entry->file_type;
			// dentry->block = block; // can't reference block here as it gets realloc'd

			if (dentry->type == EXT2_FT_DIR && !is_dot) {
				dentry_t *d = hash_find_dentry(dentry->inode);
				if ( d == NULL) {
					// actually only that should ever happen
					if (dentry->inode == 0)
						fprintf(stderr, "got dentry with inode 0, block %lu\n", blk_nr);

					hash_add_dentry(dentry);
				} else {
					fprintf(stderr, "Oops we have the same inode twice: %lu %s \n",
							(unsigned long)dentry->inode, dentry->name);

					// keep track of hashed dentry, it will become real dir
					dentry->real_dir = d;
					d->real_dir = d;
				}
			}

			print_dir_entry(dir_entry, block);

		} else {
			offset += 1;
		}
	}
	return 0;
}

/**
 * wrapper around chdir() so we can manually keep track of a relative cwd
 * This is actually unecessary as we are already in a chroot, so it's all relative
 *
*/
int sd_chdir(const char *dirname, int updir_fd) {
	int rc;

	// .. is a special case since we could have jumped a symlink
	if ((strncmp(dirname, "..", 3) == 0)) {
		if (!updir_fd) {
			fprintf(stderr, "chdir to .. w/o updir_fd, cwd: %s, dirname: %s\n",
					cwd, dirname);
			exit(1);
		}
		if (fchdir(updir_fd) == -1) {
			fprintf(stderr, "Could not fchdir back to %s: %s\n",
					cwd, strerror(errno));
			exit (1);
		};
		close(updir_fd);
	} else {
		chdir(dirname);
	}

	if (getcwd(cwd, CWD_MAX) == NULL) {
		fprintf(stderr, "Could not get cwd:%s\n", strerror(errno));
		exit(1);
	}

	return rc;
}

/**
 * scan through the given number of blocks, starting with block-number
 * first_block
 */
static void scan_blocks(void *buf, uint64_t first_block, int nb)
{
	int i;
	uint64_t blk_nr = first_block;
	for (i = 0; i < nb; i++) {
		scan_block(buf + i * opts.block_size, blk_nr);
		blk_nr++;
	}
}

/**
 * A child claims to belong to a parent, check if the parent knows about the 
 * child directory
 */
static bool parent_has_our_block(dentry_t *parent_dentry, int64_t child_inode)
{
	dentry_t *dentry = parent_dentry;
	
	while (dentry) {
		if (dentry->inode == child_inode) {
			if (dentry->type != EXT2_FT_DIR) {
				// type mismatch, expected directory, check OST data
				if (hash_find_fid(dentry->inode)) {
					// OST knows about this inode, so it can't be
					// a directory
					return false;
				}
			}
			return true; // sanity test passed :)
		}
			
		dentry = dentry->next;
	}
	
	return false;
}

/**
 * associate blocks that belong together
 */
static void associate_blocks(dir_block_table_t *blocks)
{
	uint64_t i;

	printf("associating %d blocks...", blocks->n_entries);
	for (i = 0; i < blocks->n_entries; i++) {
		block_t *block = &blocks->table[i];
		dentry_t * parent_dentry;

		if (i % 100000 == 0) 
			printf("%d..", i);
		
		if (block->dir_inode == -1) {
			fprintf(stderr, "block %lld has unknown inode #, not associating\n",
					(long long int)block->number);
			continue;
		}
	
		parent_dentry = hash_find_dentry(block->dir_inode);
		if (!parent_dentry) {
			// parent not found, reset it
			/* fprintf(stderr, "block %lld parent %ld not found\n", 
					(long long int)block->number, block->parent); */
			block->parent = -1;
			continue;
		}
		if (block->dir_inode != parent_dentry->inode) {
			// just a sanity test if we did something wrong
			fprintf(stderr, "inode mismatch %lu vs. %lu\n",
					block->dir_inode, parent_dentry->inode);
		}
		if (parent_dentry->type != EXT2_FT_DIR) {
			fprintf(stderr, "%lu: Expected directory, but type is %d\n",
					block->dir_inode, parent_dentry->type);
		}
		
		if (!parent_has_our_block(parent_dentry, block->dir_inode)) {
			fprintf(stderr, "Parent %s (%lu) doesn't know about us (%lu)\n",
					parent_dentry->name, parent_dentry->inode, block->dir_inode);
			block->parent = -1;
			continue;
		}
				
		struct childs *childs = &parent_dentry->childs;
		childs->child = realloc(childs->child, sizeof(struct block_t *) * (childs->num + 2));
		if (childs->child == NULL) {
			fprintf(stderr, "childs->child realloc failed: %s\n",
					strerror(errno));
			exit(1);
		}
		childs->child[childs->num] = block;
		childs->num++;
		
		block->name = strdup(parent_dentry->name);
		if (block->parent == -1) {
			fprintf(stderr, "Associated block %lu without .. to parent %lu\n",
					block->number, parent_dentry->inode);
			block->parent = parent_dentry->inode;
		}
	}
	printf("done\n");
}

/**
 * create a file
 * return 1 if file sucessfully created
 */
static int create_file(dentry_t *dentry, block_t *block, int dir_level)
{
	int res, lov_size, good_res = 1;
	struct stat file_stat;
	ost_fid_t *ost_fid = hash_find_fid(dentry->inode);
	
	if (!ost_fid) {
		fprintf(stderr, "Could not find OST data for %s/%s (%lu) "
			"skipping file\n",
			cwd, dentry->name, dentry->inode);
		return -1;
	}
	// deal with this before symlinkage
	if (dir_level > 0) {
		// We are in a subdirectory and while we know uid and gid
		// for files from OSTs, we don't know for the directory 
		// itself. Rather probably uid and gid of the directory
		// also match those of the file. We only do this for 
		// level > 0, since we don't want to change the owner of
		// "/"
		if (block->uid == -1) {
			chown(".", ost_fid->uid, ost_fid->gid);
			block->uid = ost_fid->uid;
			block->gid = ost_fid->gid;
		} else if (block->uid != ost_fid->uid) {
			// mixed ownership within a directory is unusual
			block->mixed = 1;
		}
	}
	if (ost_fid->dentry != NULL) {
		char tgt_buf[CWD_MAX], link_buf[CWD_MAX];
		fmt_dentry_path(tgt_buf, ost_fid->dentry);
		snprintf(link_buf, CWD_MAX - 1, "/%s/%s", cwd, dentry->name);
		if (link(tgt_buf, link_buf) < 0)
			fprintf(stderr, "error: linking %s -> %s: %s\n",
					link_buf, tgt_buf, strerror(errno));
		printf("hardlink: %s -> %s\n", link_buf, tgt_buf);
		return 1;
	}
	ost_fid->dentry = dentry;

	int fd = creat(dentry->name, FILE_MODE);
	if (fd == -1) {
		fprintf(stderr, "Could not create file %s/%s: %s\n",
				cwd, dentry->name, strerror(errno));
		return -1;
	} 

	res = stat(dentry->name, &file_stat);
	if (res == -1) {
		fprintf(stderr, "Failed to stat %s/%s: %s\n",
			cwd, dentry->name, strerror(errno));
		return -1;
	}
	
	lov_size = sizeof(struct lov_user_md_v1) 
			+ sizeof(struct lov_user_ost_data_v1) 
			* ost_fid->fid.lmm_stripe_count;
	res = fsetxattr(fd, "trusted.lov", &ost_fid->fid, lov_size, 0);
	if (res == -1) {
		fprintf(stderr, "Failed to create xattr on %s/%s: %s\n",
			cwd, dentry->name, strerror(errno));
	}
	fchown(fd, ost_fid->uid, ost_fid->gid);

	struct timeval timevals[2] = { {ost_fid->timestamp, 0}, 
		{ost_fid->timestamp, 0} };
	futimes(fd, timevals);
	close(fd);
	
	return 1;
}

/**
 * walk_block found wants to create a directory
 * 
 * @dentry - the current directory entry
 * @cwd - current working directory
 */
static int create_dir(dentry_t *dentry, int dir_level)
{
	int j;
	int created = 0;
	char *dirname = dentry->name;

	if (dentry->create_stage) {
		fprintf(stderr, "Already created this dir: %s/%s\n", cwd, dentry->name);
		return -1;
	}
	dentry->create_stage = 1;

	if (dentry->real_dir != NULL) {
		if (dentry->real_dir != dentry) {
			if (dentry->real_dir->create_stage == 2) {
				// if the real dir is created, process this after the block
				// we can't create before, because block might move
				queue_link(dentry);
			} else {
				// process this when the real dir is made
				dentry->link_waiter_next = dentry->real_dir->link_waiter_next;
			}
			// this is a symlink, return 1 so we don't delete the parent
			return 1;
		} else {
			// we are creating the real dir, queue this to process waiters
			queue_link(dentry);
		}
	} 

	if (!dentry->childs.child) {
		fprintf(stderr, "Directory %s/%s has no blocks associated, skipping\n",
				cwd, dentry->name);
		return -1; // no child, so no need to create this directory
	}
		

	struct childs *childs = &dentry->childs;
				
	for (j = 0; j < childs->num; j++) {
		created +=  walk_block(childs->child[j]);
	}

	return created;
}

/** 
 * assign a name based on the inode or block number for this block,
 * if it doesn't have a real name yet
 */
static char *block_name(block_t *block)
{
	if (block->name == NULL) {
		char name[255];
		if (block->dir_inode != -1 && block->dir_inode != 0)
			snprintf(name, 254, "dirinum_%llu", (long long unsigned)block->dir_inode);
		else {
			snprintf(name, 254, "block%lu", block->number);
		}
		block->name = strdup(name);
	}
	
	return block->name;
}

int create_symlink(const char *tgt_path, const char *link_path) {
	char tgt_buf[CWD_MAX], rel_part[512];
	const char *p;
	char last = 0;
	int rel_len = 0, first = true;
	
	// build relative path (relative to link)
	for (p = link_path; *p; p++) {
		if (last != '/' && *p == '/') {
			if (!first) {
				// skip initial /
				rel_part[rel_len++] = '.';
				rel_part[rel_len++] = '.';
				rel_part[rel_len++] = '/';
			} else {
				first = false;
			}
		}
		last = *p;
	}
	rel_part[rel_len] = 0;
	snprintf(tgt_buf, CWD_MAX, "%s%s", rel_part, tgt_path);
	tgt_buf[CWD_MAX - 1] = 0;

	return symlink(tgt_buf, link_path);
}

void symlink_dentries(dentry_t *tgt_dent, dentry_t *link_dent) {
	char tgt_buf[CWD_MAX], link_buf[CWD_MAX];
	fmt_dentry_path(tgt_buf, tgt_dent);
	fmt_dentry_path(link_buf, link_dent);
	if (create_symlink(tgt_buf, link_buf) < 0) {
		fprintf(stderr, "error: creating symlink %s -> %s: %s\n",
				link_buf, tgt_buf, strerror(errno));
	} else {
		printf("symlink: %s -> %s\n", link_buf, tgt_buf);
	}
}

static void process_links() {
	while (block_symlink_p) {
		// deal with directories and symlinks
		// hardlinks already created in create_File
		if (block_symlink_p->real_dir) {
			// process real dir's waiters
			if (block_symlink_p == block_symlink_p->real_dir) {
				dentry_t *p = block_symlink_p->link_waiter_next;
				while (p) {
					symlink_dentries(block_symlink_p->real_dir, p);
					p = p->link_waiter_next;
				}
				block_symlink_p->create_stage = 2;
			} else {
				// this is a symlink, make it
				if (block_symlink_p->real_dir->create_stage != 2) {
					fprintf(stderr, "symlink pointing to not created dir\n");
				}
				symlink_dentries(block_symlink_p->real_dir, block_symlink_p);
			}
		}
		block_symlink_p = block_symlink_p->symlink_next;
	}
}

/**
 * Walk along directory blocks to build the filesystem dir/file tree.
 * Each block represents a directory. We already associated blocks to form a 
 * directory tree, so this function can be called recursively.
 * Return value is the number of entries we created for this block
 */
static unsigned walk_block(block_t *block)
{
	dentry_t *dentry;
	int n_entries = 0;
	int res;

	// save current path for recall
	int updir_fd = open(".", O_RDONLY);
	
	// increased each time we chdir() into a subdir and decreased on leaving it
	static int dir_level = 0; 

	// keep track of the top level block
	static block_t *cur_tl_block;

	if (block == NULL) {
		fprintf(stderr, "Error trying to walk NULL block\n");
		return 0;
	}

	if (dir_level == 0) {
		cur_tl_block = block;
	} else {
		block->tl_block = cur_tl_block;
	}

	if (block->walked) {
		fprintf(stderr, "Already walked block %s (%lu)\n", 
				block->name, block->number);
		return 0;
	}

	block->walked = 1;
	block_name(block);
	block->cwd = strdup(cwd);

	if (mkdir(block->name, DIR_MODE) == -1 && errno != EEXIST) {
		fprintf(stderr, "Could not create dir %s/%s: %s\n",
				cwd, block->name, strerror(errno));
		return 0;
	} 

	if (sd_chdir(block->name, 0) == -1) {
		fprintf(stderr, "Could not chdir into %s\n", block->name);
		return 0;
	}

	dir_level++; // successful chdir, so increase level

	dentry = block->first;

	while (dentry) {
		if (dentry->name == NULL) {
			fprintf(stderr, "dentry %lld has no name, block %s (%lu), level %d\n", 
					dentry->inode, block->name, block->number, dir_level);
			dentry = dentry->next;
			continue;
		}

		// ignore "."
		if ((strncmp(dentry->name, ".", 1) == 0)
				&&   strlen(dentry->name) == 1) {
			dentry = dentry->next;
			continue;
		}

		// ignore ".."
		if ((strncmp(dentry->name, "..", 2) == 0)
				&&   strlen(dentry->name) == 2) {
			dentry = dentry->next;
			continue;
		}

		// TODO: need to check the OST data if the filetype is correct

		dentry->block = block;
		switch (dentry->type) {
		case EXT2_FT_REG_FILE:
			res = create_file(dentry, block, dir_level);
			if (res != -1)
				n_entries++;
			break;
		case EXT2_FT_DIR:
			res = create_dir(dentry, dir_level);
			if (res > 0) {
				// if there is a dir block, see if it got a uid
				if (block->uid == -1 && dentry->childs.child) {
					struct childs *childs = &dentry->childs;
					int j;
					for (j = 0; j < childs->num; j++) {
						if (childs->child[j]->uid != -1) {
							block->uid = childs->child[j]->uid;
							block->gid = childs->child[j]->gid;
							break;
						}
					}
				}	
				n_entries++;
			}
			break;
		default:
			fprintf(stderr, "ignoring create action for type %d (%s/%s)\n",
					dentry->type, cwd, dentry->name);
		}
		dentry = dentry->next;
	}

	// update cwd
	sd_chdir("..", updir_fd);
	
	if (n_entries < 1) 
		rmdir(block->name); // delete empty directories
	
	dir_level--; // successful chdir, so decrease level
	if (dir_level == 0 && n_entries > 0) {
		static const char mixed[] = "mixed/";
		static const char unknown[] = "unknown/";
		static const char blank[] = "";
		const char *prefix;
		char uid_dir[128];

		if (block->uid == -1) {
			prefix = unknown;
		} else if (block->mixed) {
			prefix = mixed;
		} else {
			prefix = blank;
		}
		
		snprintf(uid_dir, 128, "%suid_%lu", prefix, block->uid);
		int res = mkdir(uid_dir, DIR_MODE);
		if (res == -1 && errno != EEXIST) {
			fprintf(stderr, "Failed to create %s: %s\n", 
				uid_dir, strerror(errno));
		} else {
			char dest_dir[255];
			int i = 0;

			snprintf(dest_dir, 255, "%s/%s", uid_dir, block->name);
			res = rename(block->name, dest_dir);

			// move duplicate names out of the way
			while (res == -1 && (errno == ENOTEMPTY || errno == EEXIST)) {
				snprintf(uid_dir, 128, "%suid_%lu-%d", prefix, block->uid, i++);
				snprintf(dest_dir, 255, "%s/%s", uid_dir, block->name);
				mkdir(uid_dir, DIR_MODE);
				res = rename(block->name, dest_dir);
			}

			if (res == -1) {
				fprintf(stderr, "Failed to move %s to %s: %s\n",
						block->name, uid_dir, strerror(errno));
			}

			free(block->cwd);
			block->cwd = strdup(uid_dir);
			if (!block->cwd) {
				fprintf(stderr, "Failed to strdup %s [block %lu]\n", uid_dir, block->number);
			}
			process_links();

		} 
		printf("dirname: %s uid_dir: %s\n", block->name, uid_dir);
	}
	return n_entries;
}

/**
 * process the blocks table
 */
static void walk_blocks(dir_block_table_t *blocks)
{
	uint64_t i;

	if (chdir(opts.outputdir)) {
		fprintf(stderr, "Could not enter outputdir %s\n",
			opts.outputdir);
			exit(1);
	}
	
	if (chroot(".")) {
		fprintf(stderr, "Could not chroot() outputdir %s\n",
				opts.outputdir);
		exit(1);
	}

	if (mkdir("mixed", DIR_MODE)) {
		fprintf(stderr, "Could not create mixed dir\n");
	}
	if (mkdir("unknown", DIR_MODE)) {
		fprintf(stderr, "Could not create unknown dir\n");
	}

	printf("walking %d blocks...", blocks->n_entries);
	for (i = 0; i < blocks->n_entries; i++) {
		block_t *block = &blocks->table[i];

		if (i % 100000 == 0) 
			printf("%d..", i);

		if (block->parent != -1) 
			continue; // it has a parent so is a subdir, not handled here
		
		// block does not have a parent, so we need to create a
		// directory for it in "/"
		
		// TODO quite some code duplication to create_dir()
		
		block_name(block);

		walk_block(block);
	}
}

int main(int argc, char **argv)
{
	ext2_filsys fs;
	int res;
	int flags = 0;
	uint64_t i, inode_blocks_per_group;
	void *buf;
	int nblocks = 256; // try 1MB reads
	
	cwd[0] = 0;

	parse_opts(argc, argv);
	
	//read_ost_mapping(opts.mapping_file);
	read_ost_fid(opts.ost_data_file);

	buf = malloc(opts.block_size * nblocks);
	if (!buf) {
		fprintf(stderr, "Malloc failed: %s\n",
				strerror(errno));
		exit(1);
	}

	realloc_blocks(1); // initial allocation

	res = ext2fs_open (opts.fname, flags, opts.sb,
			opts.block_size, unix_io_manager, &fs);
	if (res) {
		fprintf(stderr, "%s: Could not find valid filesystem superblock.\n",
				opts.fname);
		exit (1);
	}

	ext2fs_read_bitmaps (fs);

	inode_blocks_per_group = ((fs->super->s_inodes_per_group *
				EXT2_INODE_SIZE(fs->super)) +
			EXT2_BLOCK_SIZE(fs->super) - 1) /
		EXT2_BLOCK_SIZE(fs->super);

	// scan for directory entries
	for (i = 0; i < fs->group_desc_count; i++) {
		// we start to scan for directory entries after the last inode table block
		uint64_t first_block = ext2fs_group_first_block(fs, i);
		uint64_t last_block = ext2fs_group_last_block(fs, i);

		int nb = nblocks; // the real number of blocks to read
		uint64_t blk = first_block;
		
		fprintf(stderr, "Group %lu, first block: %lu, last block: %lu\n", i, first_block, last_block);
		
		while (blk < last_block) {
			if (blk + nb > last_block) 
				nb = last_block - blk;
				
			if (io_channel_read_blk64(fs->io, blk, nb, buf) != 0) {
				fprintf(stderr, "Failed to read block %lu to %lu\n",
					blk, blk + nb);
				break;
			}
			scan_blocks(buf, blk, nb);
			blk += nb;
		}
		printf("Group %lu/%d done\n", i, fs->group_desc_count - 1);
		fflush(NULL);
	}

	associate_blocks(&blocks);
	fflush(NULL);
	walk_blocks(&blocks);
	fflush(NULL);

	printf("\n\nHave %llu dir entry blocks\n", (long long unsigned)blocks.n_entries);

	return 0;
}

/* vim: set noet ts=4 sw=4: */
